import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * 对称二叉树：给定一棵树判断是否是对称二叉树
 */
public class LCTree {
    public static void main(String[] args) {
//        TreeNode A = new TreeNode("A");
//        TreeNode B = new TreeNode("B");
//        TreeNode C = new TreeNode("C");
//        TreeNode D = new TreeNode("D");
//        TreeNode E = new TreeNode("E");
//        TreeNode F = new TreeNode("F");
//        TreeNode G = new TreeNode("G");
//        TreeNode H = new TreeNode("H");
//        TreeNode I = new TreeNode("I");
//        TreeNode J = new TreeNode("J");
//        TreeNode K = new TreeNode("K");
//
//        A.setLeft(B);
//        A.setRight(C);
//
//        B.setLeft(D);
//        B.setRight(E);
//
//        D.setLeft(G);
//        E.setLeft(H);
//        E.setRight(I);
//
//        C.setRight(F);
//        F.setLeft(J);
//        F.setRight(K);
//        System.out.println(isSymmetric(A));

        TreeNode A = new TreeNode(5);
        TreeNode B = new TreeNode(4);
        TreeNode C = new TreeNode(8);
        TreeNode D = new TreeNode(11);
        TreeNode E = new TreeNode(13);
        TreeNode F = new TreeNode(4);
        TreeNode G = new TreeNode(7);
        TreeNode H = new TreeNode(2);
        TreeNode I = new TreeNode(1);

        A.setLeft(B);
        A.setRight(C);

        B.setLeft(D);

        D.setLeft(G);
        D.setRight(H);
        C.setLeft(E);
        C.setRight(F);
        F.setRight(I);
        System.out.println(hasPathSum(A,22));
    }


    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public static class TreeNode{
        private Object value;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(Object value){
            this.value = value;
        }
    }

    public static boolean isSymmetric(TreeNode root) {
        if(null == root){
            return true;
        }

        //从两个子节点开始判断
        return isSymmetricHelper(root.left, root.right);
    }

    public static boolean isSymmetricHelper(TreeNode left, TreeNode right) {
        if(left == null && right == null){
            return true;
        }

        if(left == null || right == null || left.getValue() != right.getValue()){
            return false;
        }

        return isSymmetricHelper(left.left,right.right) && isSymmetricHelper(left.right,right.left);
    }


    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }

        if(root.left == null && root.right == null){
            return (int)root.value == targetSum ;
        }

        return hasPathSum(root.left,targetSum-(int)root.value) || hasPathSum(root.right,targetSum-(int)root.value);
    }
}
